package com.spirng.leetcode.day08;

import java.util.ArrayList;
import java.util.List;

public class restoreIp {
    public static void main(String[] args) {
//        String s="ad";
//        String substring = s.substring(0,1);
//        System.out.println(substring);
        restoreIp restoreIp = new restoreIp();
        restoreIp.restoreIpAddresses("25525511135");
    }
    ArrayList list=new ArrayList<String>();
    public List<String> restoreIpAddresses(String s) {
        backtracking(s,0,0);
        return list;
    }
    public void backtracking(String s,int offSize,int point){
        if(point==3){
            if(isValid(s,offSize,s.length()-1)){
                list.add(s);
            }
            return;
        }
        for (int i = offSize; i < s.length(); i++) {
            if(isValid(s,offSize,i)){
                s=s.substring(0,i+1)+"."+s.substring(i+1,s.length());
                point++;
                backtracking(s,i+2,point);
                point--;
                s=s.substring(0,i+1)+s.substring(i+2,s.length());
            }else {
                break;
            }
        }
    }
    public boolean isValid(String s,int start,int end){
        if(start-end>4){
            return false;
        }
        String substring = s.substring(start, end + 1);

        for (int i = 0; i < substring.length(); i++) {

        }
        if(substring==""){
            return false;
        }
        int i = Integer.parseInt(substring);
        if(s.charAt(start)=='0'&&start!=end){
            return false;
        }
        if(i<0||i>255){
            return false;
        }
        return true;
    }
}
